/** @file
 * IPRT - AVL Trees.
 */

/*
 * Copyright (C) 2006-2020 Oracle Corporation
 *
 * This file is part of VirtualBox Open Source Edition (OSE), as
 * available from http://www.virtualbox.org. This file is free software;
 * you can redistribute it and/or modify it under the terms of the GNU
 * General Public License (GPL) as published by the Free Software
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
 * VirtualBox OSE distribution, in which case the provisions of the
 * CDDL are applicable instead of those of the GPL.
 *
 * You may elect to license modified versions of this file under the
 * terms and conditions of either the GPL or the CDDL or both.
 */

#ifndef IPRT_INCLUDED_avl_h
#define IPRT_INCLUDED_avl_h
#ifndef RT_WITHOUT_PRAGMA_ONCE
# pragma once
#endif

#include <stdint.h>
#include "CommonDef.h"

RT_C_DECLS_BEGIN

/** @defgroup grp_rt_avl    RTAvl - AVL Trees
 * @ingroup grp_rt
 * @{
 */

/** @name AVL tree of uint32_t
 * @{
 */

/** AVL key type. */
typedef uint32_t    AVLU32KEY;

/** AVL Core node. */
typedef struct _AVLU32NodeCore
{
    struct _AVLU32NodeCore *pLeft;      /**< Pointer to left leaf node. */
    struct _AVLU32NodeCore *pRight;     /**< Pointer to right leaf node. */
    AVLU32KEY               Key;        /**< Key value. */
    unsigned char           uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
} AVLU32NODECORE, *PAVLU32NODECORE, **PPAVLU32NODECORE;

/** A tree with uint32_t keys. */
typedef PAVLU32NODECORE     AVLU32TREE;
/** Pointer to a tree with uint32_t keys. */
typedef PPAVLU32NODECORE    PAVLU32TREE;

/** Callback function for AVLU32DoWithAll() & AVLU32Destroy().
 *  @returns IPRT status codes. */
typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
typedef AVLU32CALLBACK *PAVLU32CALLBACK;


/*
 * Functions.
 */
RTDECL(bool)            RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
RTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
RTDECL(int)             RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
RTDECL(int)             RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);

/** @} */

RT_C_DECLS_END

#endif /* !IPRT_INCLUDED_avl_h */

